The transmission of binary computer data involves the introduction of errors, which must be detected and corrected, if possible. Although the difference between the two binary values, zero and one, seems clear, like the difference between black and white, in practice an electronic device may have difficulty distinguishing the difference. The difference between binary values may be detected as a voltage difference, but electronic noise in a circuit can interfere and render the difference less certain. This uncertainty must be dealt with. One option is to reject the data input and request retransmission. However, this is impossible with some fast flowing digital signals with substantial volume, such as digital TV, and is impractical in many situations. Accordingly, error correction systems have been developed to detect and correct errors. Communication systems often use forward error correction to correct errors induced by noise in the channel. In such systems, the error correction occurs at the receiver. One such system is parity check coding. One example of parity check coding is “low density parity check” coding (“LDPC”).
Forward error correction consists of adding redundancy to data. Block codes, such as the LDPC codes, segment the data into blocks. These blocks have additional bits added according to a specified algorithm, to create a codeword. This codeword is transmitted to the receiver over the channel. The data that is transmitted is binary in nature, meaning that it is either a logical “1” or a logical “0”. Noise is added by the channel, and the receiver detects each of the bits of the codeword and makes a best initial determination as to whether the bit is a logical 1 or 0. The receiver might also have the ability to assign a confidence in its guess. These guesses are called soft bits.
When a receiver gets a codeword, it is processed. The coding information added to original data is used to detect and correct errors in the received signal and thereby recover the original data. For received values with errors, the decoding system will attempt to recover or generate a best guess as to the original data.
As noted above, the receiver can reject data input containing errors. Retransmission may increase the reliability of the data being transmitted or stored, but such a system demands more transmission time or bandwidth or memory, and in some applications, such as digital TV signals, it may be impossible with current technology. Therefore, it is highly desirable to perfect error detection and correction of transmitted data.
LDPC systems use an iterative decoding process which is particularly suitable for long codewords. In general, LDPC codes offer greater coding gains than other, currently available codes. The object is to use parallel decoding in the LDPC's iterative process to increase speed. In order to accomplish this, the inherent parallelism of an LDPC code must be found and exploited. There is also a need to reduce the amount of memory accesses and total memory required per iteration. To make the LDPC coding work as efficiently and quickly as possible, careful attention must be drawn to the storage of data and routing the data to the storage during the iterations.
U.S. Pat. No. 6,633,856 to Richardson et al. (“Richardson”), discloses two LDPC decoder architectures, a fast architecture and a slower architecture. In the slow architecture, a single iteration consists of two cycles. There is an edge memory consisting of one location for each edge in the Tanner Graph or, equivalently, there is one location for each 1 in the H matrix. There is also an input buffer which requires a memory location for each input variable, or equivalently, there is a memory location for each column of the H matrix. The two memories do not require the same resolution, the high resolution memory is the edge memory, and the low resolution memory is the input buffer. In the fast architecture, a single iteration consists of a single memory cycle. There are two edge memories and a single input buffer required.